#include "big_int.h"
#include <iostream>
#include <cmath>
#include <string>
#include <cstdlib>

using std::max;
using std::string;
using std::cerr;
using std::cout;
using std::exception;

big_int::big_int(): number(container(1)), length(1), sign(0)
{
}

big_int::big_int(int64 x) : number(container(1)), length(1)
{
	number[0] = (x < 0 ? -x : x);
	sign = (x < 0);
	repair(*this);
}

big_int::big_int(const container& number_, bool sign_)
{
	sign = sign_;
	length = number_.size();
	number = number_;
	repair(*this);
}

big_int::big_int(string s)
{
	bool sign_ = false;
	if (s[0] == '-') 
	{
		sign_ = true;
		s = s.substr(1, s.size() - 1);
	}
	int size_ = s.size();
	int length_ = (size_ - 1) / big_int::base_length + 1;
	number = container(length_);
	for (int i = size_ - 1, j = 0; i >= 0; i -= big_int::base_length, j++)
		if (i >= big_int::base_length)
			number[j] = atol(s.substr(i - big_int::base_length + 1, big_int::base_length).c_str());
		else
			number[j] = atol(s.substr(0, i + 1).c_str());
	*this = big_int(number, sign_);
	repair(*this);
}

big_int& big_int::operator=(const big_int& other) {
	sign = other.sign;
	length = other.length;
	number = other.number;
	return *this;
}

void big_int::swap(big_int& other)
{
	::swap(*this, other);
}

void swap(big_int& a, big_int& b)
{
	std::swap(a.sign, b.sign);
	std::swap(a.length, b.length);
	a.number.swap(b.number);
}

bool operator==(const big_int& a, const big_int& b)
{
	return !((a < b) || (a > b));
}

bool operator !=(const big_int& a, const big_int& b)
{
	return !(a == b);
}

bool big_int::operator<(const big_int& other) const
{
	if (sign != other.sign)
		return sign;
	if (sign)
		return abs(*this) > abs(other);
	if (length != other.length)
		return length < other.length;
	for (int i = length - 1; i >= 0; i--)
		if (number[i] != other.number[i])
			return number[i] < other.number[i];
	return false;
}

bool operator<=(const big_int& a, const big_int& b)
{
	return (a < b) || (a == b);
}

bool operator>(const big_int& a, const big_int& b)
{
	return b < a;
}

bool operator>=(const big_int& a, const big_int& b)
{
	return (a > b) || (a == b);
}

void repair(big_int& a)
{
	int size_ = a.length;
	for (int i = 0; i < size_; i++) {
		if (a.number[i] < 0)
		{
			if (i + 1 > a.length - 1) 
			{
				a.number.resize(i + 2);
				a.length++;
			}
			a.number[i] += a.base;
			a.number[i + 1]--;
		} else
		if (a.number[i] >= a.base)
		{
			if (i + 1 > a.length - 1) 
			{
				a.number.resize(i + 2);
				a.length++;
			}
			a.number[i + 1] += a.number[i] / a.base;
			a.number[i] %= a.base;
		}
	}
	while (a.length > 1 &&  a.number[a.length - 1] == 0)
		a.length--;
		
	if (a.number[a.length - 1] < 0) {
		for (int i = 0; i < a.length; i++)
			a.number[i] *= (-1);
		a.sign = !a.sign;
		repair(a);
	}
	a.number.resize(a.length);
	if ((a.length == 1) && (a.number[0] == 0))
		a.sign = 0;
}

big_int& big_int::operator +=(const big_int& other)
{
	length = max(length, other.length);
	number.resize(length);
	for (int i = 0; i < length; i++)
		number[i] = (const_cast<const container&>(number)[i] *(sign ? -1 : 1) + const_cast<const container&>(other.number)[i] * (other.sign ? -1 : 1));
	sign = false;
	repair(*this);
	return *this;
}

big_int operator -(big_int other)
{
	other.sign = !other.sign;
	repair(other);
	return other;
}

big_int abs(big_int other)
{
	other.sign = false;
	return other;
}

big_int& big_int::operator -=(const big_int& other)
{
	return *this += -other;
}

big_int& big_int::operator *=(const big_int& other)
{
	int length_ = length + other.length;
	bool sign_ = sign ^ other.sign;
	container number_ = container(length_);
	for (int i = 0; i < length; i++)
		for (int j = 0; j < other.length; j++) 
			number_[i + j] += const_cast<const container&>(number)[i] * const_cast<const container&>(other.number)[j];
	big_int tmp = big_int(number_, sign_);
	swap(tmp);
	repair(*this);
	return *this;
}

big_int big_int::operator <<(const int shift) const
{
	int length_ = length + shift;
	container result_ = container(length_);
	for (int i = shift; i < length_; i++)
		result_[i] = number[i - shift];
	big_int result = big_int(result_, sign);
	repair(result);
	return result;
}

big_int big_int::operator >>(const int shift) const
{
	int length_ = length - shift;
	if (length <= 0)
		return big_int(0);
	container result_ = container(length_);
	for (int i = 0; i < length_; i++)
		result_[i] = number[i];
	big_int result = big_int(result_, sign);
	repair(result);
	return result;
}

big_int& big_int::operator /=(big_int other)
{
	/*if (other == big_int(0))
		throw exception("Division by zero");
	*/
	bool sign_ = sign ^ other.sign;
	(*this) = abs(*this);
	other = abs(other);
	if (other > (*this)) 
		return *this = big_int(0);
	int length_ = length - other.length + 1;
	container result = container(length_);
	if (other.number[other.length - 1] < 0.75 * base)
	{
		int64 multip = base / (other.number[other.length - 1] + 1);
		(*this) *= big_int(multip);
		other *= big_int(multip);
	}
	big_int tmp;
	int64 approx;
	for (int i = length_- 1; i > -1; i--)
	{
		if (length == 1)
		{
			if((*this) >= other)
			{
				result[i] = number[i] / other.number[i];
				number[i] -= other.number[i] * result[i];
			}

			break;
		}
		approx = (const_cast<const container&>(number)[length - 1] * base + const_cast<const container&>(number)[length - 2] ) / const_cast<const container&>(other.number)[other.length - 1];
		for (int64 j = approx - 2; j < approx + 3; j++)
		{
			tmp = big_int((big_int(j) * other) << i);
			if (tmp > (*this))
				break;
			result[i] = j;
		}
		if (result[length_ - 1] == 0)
			length_--;
		else
			(*this) -= (big_int((big_int(result[i]) * other) << i));
	}
	if ((other <= *this) && (*this < big_int(2) * other))
		result[0] += 1;
	big_int result_ = big_int(result, sign_);
	repair(result_);
	return *this = result_;
}

big_int& big_int::operator %=(const big_int& other)
{
	return (*this) -= ((*this) / other) * other;
}

big_int operator +(big_int a, const big_int& b)
{
	return a += b;
}

big_int operator -(big_int a, const big_int& b)
{
	return a -= b;
}

big_int operator *(big_int a, const big_int& b)
{
	return a *= b;
}

big_int operator /(big_int a, const big_int& b)
{
	return a /= b;
}

big_int operator %(big_int a, const big_int& b)
{
	return a %= b;
}

std::istream& operator>>(std::istream& is, big_int& result)
{
	string s;
	while (!is.eof() && isspace(is.peek()))
		is.get();
	if (is.peek() == '+')
		is.get();
	else if (is.peek() == '-')
		s.push_back(is.get());
	if (is.eof())
	{
		return is;
	}
	if (!isdigit(is.peek()))
	{
		is.seekg(0, std::ios::end);
		is.setstate(std::ios::failbit);
		return is;
	}
	while (!is.eof() && isdigit(is.peek()))
		s.push_back(is.get());
	result = big_int(s);
	return is;
}

std::ostream& operator<<(std::ostream& os, const big_int& value)
{
	int n = value.length;
	if (value.sign)
		os << "-";
	os << value.number[n - 1];
	for (int i = n - 2; i >= 0; i--)
	{
		int64 current = value.number[i];
		int64 tmp = current;
		int length_ = 0;
		for (length_ = 0; tmp > 9; tmp /= 10, length_++);
		for (int i = 0; i < big_int::base_length - length_ - 1; i++)
			os << "0";
		os << current;
	}
	return os;
}